1. Field of the Invention
The present invention relates to a method and a data processing device, for executing either of division and remainder instructions with efficiency, each of the division and remainder instructions having a code in which information on the size of dividend data is placed.
2. Description of the Prior Art
An instruction set for 32-bit microprocessors can have division and remainder instructions. In either of division and remainder instructions, an operand that can be either one of the divisor and the dividend is handled as a 32-bit binary value.
Referring now to FIG. 10, there is illustrated a diagram showing the code of each of division and remainder instructions included in an instruction set provided by a prior art data processing device. In the figure, OP1 denotes a first operand code, OP2 denotes a second operand code, R1 denotes a destination register identifier, R2 denotes a source register identifier, and C denotes a constant number portion.
In general, each of division and remainder instructions provided by a data processing device can identify both a destination register and a source register using the destination and source register identifiers thereof. For example, division instructions can identify a register storing the dividend with the destination register identifier R1 thereof, identify another register storing the divisor with the source register identifier R2 thereof, and store the division result into the register identified by the destination register identifier R1. Each of division and remainder instructions does not use information placed in the constant number portion C.
Most prior art data processing devices adopt nonrestoring division as a division algorithm. Although the nonrestoring division is a typical division algorithm, one iteration of division processing computes only one-bit output and therefore much time is spent in computing all one-bit outputs in order to completely perform the division processing, thus reducing the division processing speed.
Referring next to FIG. 11, there is illustrated a flow diagram showing a division algorithm adopted by prior art data processing devices. FIG. 12 shows a block diagram showing hardware required for performing the division algorithm as shown in FIG. 11. In FIG. 12, reference numeral 121 denotes a 32-bit ALU for performing arithmetic operations, numeral 122 denotes a remainder register for storing a remainder, the right-hand 32 bits of the remainder register constituting an extended register, numeral 123 denotes a register, which will be referred to as divisor register, for storing a divisor, and numeral 124 denotes a control circuit for controlling the ALU 121 and the remainder register 122.
Next, a description will be made as to a flow of division processing based on the nonrestoring division in prior art data processing devices, assuming that both the dividend and the divisor are positive numbers.
First, the control circuit 124, in step ST111, stores the dividend data in the extended register, i.e., the right-hand half of the remainder register 122, and then sets all of the left-hand 32 bits of the remainder register 122 to zero. Furthermore, the control circuit 124 causes the remainder register 122 to shift the data loaded thereinto left one bit position.
The ALU 121 then, in step ST112, subtracts the contents of the divisor register 123 from the contents of the left-hand half of the remainder register 122, and then loads the subtraction result into the left-hand half of the remainder register 122.
The control circuit 124 then, in step ST113, determines whether or not the remainder stored in the left-hand half of the remainder register 122 is equal to or greater than zero. If the remainder is equal to or greater than zero, the control circuit advances step ST115 in which it causes the remainder register 122 to shift the contents thereof left one bit position and sets a new bit at the far-right position of the remainder register 122 to one. After that, the control circuit 124 advances to step ST116.
In performing step ST113, if the remainder is less than zero, the control circuit advances step ST114 in which the ALU 121 adds the contents of the divisor register 123 to the data stored in the left-hand half of the remainder register 122 so as to return the data stored in the left-hand half of the remainder register 122 to its previous value stored before step ST112, and then stores the addition result in the left-hand half of the remainder register 122. After that, the control circuit 124 causes the remainder register 122 to shift the contents thereof left one bit position and sets a new bit at the far-right position of the remainder register 122 to zero. The control circuit 124 then advances to step ST116.
The loop iteration comprised of the above-mentioned steps ST112 to ST116 is carried out thirty-two times. In step ST116, the control circuit 124 determines whether or not the number of times that the loop iteration comprised of the plurality of steps has been done is equal to or greater than 32. If the number of times that the loop iteration comprised of the plurality of steps has been carried out is less than 32, the control circuit 124 returns to step ST112, and then repeats the above-mentioned processes. After the loop iteration has been performed thirty-two times, the control circuit 124 advances to step ST117 in which it causes the remainder register 122 to shift the data stored in the left-hand half of the remainder register 122 right one bit position.
A problem with prior art data processing devices constructed as above is that since data on which an arithmetic operation is to be performed has a fixed length of 32 bits, the number of times that the loop iteration based on the nonrestoring division is done is fixed, that is, the loop iteration must be performed thirty-two times.
According to the nonrestoring division, when data that can be handled by prior art data processing devices has a significant bit width of N bits, the number of times that the loop iteration must be performed for each of division and remainder calculations can be N that is the same as the bit width of the data. In such a prior art data processing device, since operands have a fixed length of 32 bits, the loop iteration required for each of division and remainder calculations must be done a fixed number of times, i.e., thirty-two times, even if each operand has a significant data width less than 32 bits. Either of division and remainder calculations thus needs a fixed number of clock cycles at all times. Accordingly, when an operand in either of division and remainder instructions has a significant data width less than 32 bits, some loop iterations done upon the execution of the instruction are a time-wasting. In image processing that is a typical example in which division and remainder instructions are frequently issued, data to be processed is 8 or 16 bits in length in most cases. A 32-bit data area for the dividend data thus has a significant bit width of 8 or 16 bits. In this case, although eight or sixteen loop iterations are required for performing each of division and remainder calculations based on the nonrestoring division, thirty-two loop iterations are carried out actually. In this manner, the loop iteration required for executing each of division and remainder instructions must be done thirty-two times even though the bit length of data to be processed is less than 32 bits. Accordingly, some loop iterations carried out upon the execution of each of division and remainder instructions are a time-wasting in most cases, and hence much time is spent in executing each of division and remainder instructions.
The present invention is made to overcome the above problem. It is therefore an object of the present invention to provide a method of setting a number of times that an arithmetic loop iteration based on the nonrestoring division is done for executing either of division and remainder instructions, the number of times corresponding to a significant bit width of dividend data used for either of the division and remainder instructions, and a data processing device using the method, thus reducing the number of cycles required for the execution of either of the division and remainder instructions, improving the processing speed, making it possible to handle dividend data having an arbitrary bit length, and reducing the hardware cost required for executing either of the division and remainder instructions with dividend data having an arbitrary bit length.
In accordance with one aspect of the present invention, there is provided a data processing device comprising: an instruction decoding unit for decoding a code of either a division instruction or a remainder instruction applied thereto, the instruction code having a size field for storing data size information; a control unit for receiving a decoded result from the instruction decoding unit, the decoded result indicating the data size information stored in the size field of the instruction code, and for presetting a number of times that one loop iteration comprised of steps required for executing either the division instruction or the remainder instruction is to be carried out, based on the data size information; and an arithmetic unit for performing the loop iteration for either the division instruction or the remainder instruction only the number of times preset by the control unit.
When the instruction code is a code of a division instruction, the length of dividend data can be placed, as the data size information, in the size field of the instruction code. As an alternative, a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of dividend data) can be placed, as the data size information, in the size field of the instruction code. Then the control unit can preset the number of times that the loop iteration required for executing the division instruction is to be carried out by the arithmetic unit, based on the data size information on the dividend data placed in the size field of the instruction code.
When the instruction code is a code of a remainder instruction, the length of dividend data can be placed, as the data size information, in the size field of the instruction code. As an alternative, a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of dividend data) can be placed, as the data size information, in the size field of the instruction code. Then the control unit can preset the number of times that the loop iteration required for executing the remainder instruction is to be carried out by the arithmetic unit, based on the data size information on the dividend data placed in the size field of the instruction code.
In accordance with another aspect of the present invention, there is provided a data processing device comprising: an instruction decoding unit for decoding a code of either a division instruction or a remainder instruction applied thereto, the instruction code having a size field for storing data size information; a control unit for receiving a decoded result from the instruction decoding unit, indicating the data size information stored in the size field of the instruction code, and for presetting a number of times that one loop iteration comprised of steps required for executing either the division instruction or the remainder instruction is to be carried out based on nonrestoring division, based on the data size information; an arithmetic unit for performing the loop iteration for either the division instruction or the remainder instruction based on the nonrestoring division only the number of times preset by the control unit; the control unit setting a number of bits that dividend data associated with either the division instruction or the remainder instruction is to be shifted to a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of the dividend data); the arithmetic unit shifting the dividend data left the number of bits preset by the control unit; and the dividend data that has been shifted being applied to the arithmetic unit as input data required for performing the loop iteration for either the division instruction or the remainder instruction based on the nonrestoring division.
When the instruction code is a code of a division instruction, the length of the dividend data can be placed, as the data size information, in the size field of the instruction code. As an alternative, a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of the dividend data) can be placed, as the data size information, in the size field of the instruction code.
When the instruction code is a code of a remainder instruction, the length of the dividend data can be placed in, as the data size information, the size field of the instruction code. As an alternative, a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of the dividend data) can be placed, as the data size information, in the size field of the instruction code.
In accordance with a preferred embodiment of the present invention, when data that can be handled by the data processing device is 2m (m is a positive integer) bits in length, the control unit includes an (m+1)-bit counter for counting the number of times that the loop iteration has been repeated by the arithmetic unit, presets an initial value of the (m+1)-bit counter to a value equal to (the length of data that can be handled by said data processing devicexe2x88x92the data size information), and determines that the repetition of the loop is complete when the most significant bit of the (m+1)-bit counter becomes one from zero.
In accordance with a further aspect of the present invention, there is provided a method (or algorithm) for performing either of division and remainder calculations, for use with a data processing device, the method comprising the steps of: shifting dividend data, which is associated with either a division instruction or a remainder instruction, left a predetermined number of bits corresponding to a value equal to (the length of data that can be handled by the data processing devicexe2x88x92the length of the dividend data); presetting a number of times that one loop iteration comprised of steps required for executing either the division instruction or the remainder instruction is to be carried out based on nonrestoring division to a value equal to the length of the dividend data; and applying the dividend data that has been shifted left the predetermined number of bits, as input data, to the loop being repeated based on the nonrestoring division, for executing either the division instruction or the remainder instruction.
Further objects and advantages of the present invention will be apparent from the following description of the preferred embodiments of the invention as illustrated in the accompanying drawings.